The origin of the modern keyboard as the primary method for inputting text from a human to a machine dates back to early typewriters in the 19th century. As computers were developed, it was a natural evolution to adapt the typewriter keyboard to use as the primary method for inputting text. For a skilled typist, it has remained the fastest way possible to input text into the computer.
With ongoing efforts to make computers smaller and more portable, the physical keyboard has become one of the most significant limiting factors in just how small a device can become: the physical size of the human finger is not something computer designers could change. As a result, computers for certain portable applications have been designed without a physical keyboard, and use touch-screen based input methods as the primary form of human-computer interface. (This is also the case for some applications where people are physically unable to use a keyboard, such as persons with physical disabilities.)
Input methods that are designed for portable touch-screen based devices have two primary requirements that frequently conflict with each other. The method of input must be as fast as possible and at the same time the method of input must take as little of the display screen as possible. Unfortunately, as the space taken up for input on the display screen is decreased, it becomes difficult to increase speed without adversely affecting accuracy.
In spite of a recent surge in the market for pen-based computing devices, many people who must generate text still do so with a standard keyboard. To date, pen-based computing has not replaced conventional portable laptop computers as was originally forecast, for the simple reason that text input on pen-based computers is too slow. Other devices sacrifice half of the area of the face of the device in order to include a “thumb” keyboard with miniature keys that are difficult to use, time-consuming, and error-prone. At the same time, such an approach means that the area relegated to a physical keyboard can no longer be used to provide a much larger display with correspondingly more efficient and enjoyable access to information.
Analogous to one-finger typing, the current state-of-the art for inputting using a virtual keyboard is called “point and tap”. A stylus is moved from letter to letter and a “tap” is performed by contacting the screen on the desired key to select it. This results in the need to constantly lift the stylus from the screen and set back down again, significantly slowing input. Cursive handwriting was invented to allow a better (and faster) flow from letter to letter and reduce the number of pen (or quill) lifts. In a similar way, the current invention reduces the number of taps required when inputting using an on-screen keyboard, thus speeding text entry.
The natural way for a human to create text on anything other than a machine is to “write” it by hand, so it is not surprising that handwriting recognition software has been developed to allow a user to enter text by writing on the screen of the computer. However natural, handwriting is slow. Each letter requires several strokes of the stylus, making it very inefficient. Further, with varying handwriting styles, accuracy of this software is still below user-acceptance levels (see MacKenzie, I. S., & Chang, L. (1999), A performance comparison of two handwriting recognizers. Interacting with Computers, 11, 283-297.). As mentioned above, the reliance on the use of “digital ink” by even the “latest and greatest” of computer touch-screen technology, the Tablet PC, provides clear evidence that handwriting recognition is still not good enough to satisfy most users. Furthermore, even if a completely accurate method of handwriting recognition were available, handwriting itself is simply too slow and tiring to provide a satisfactory input method (especially on a touch-screen, which does not provide the same “feel” as a pen on actual paper).
There are two large shortcomings of on-screen keyboards: first they take up valuable screen space on the computer needed for whatever task is requiring text input. Second, and more importantly, they are slow because the user is forced to tap one letter at a time—effectively reducing the user to input text in a way that is analogous to single finger typing on a regular physical keyboard.
Another factor in slowing text entry on touch-screen keyboards was the time it takes to lift the stylus from the screen and then bring it back down between each key selection (“tapping”). This is a fundamental problem in that, particularly for devices that must utilize touch-screen keyboards that are reduced in size, the additional actions of lifting the stylus and bringing it back into contact with the screen in a controlled manner drastically slow down the input process. In addition, there is a need for an input system that is generally able to determine and produce the correctly spelled word intended by the user even when the user enters an erroneous gesture (where the user made one or more errors in the attempt to enter a correctly shaped gesture for the intended word) or an incorrect gesture (where the user's conception of the spelling of the intended word is incorrect—for example, entering a gesture corresponding to the key sequence “freind” in order to input the word that is actually spelled “friend”).
The present invention allows rapid gestural input of virtually every word, with the very rare exception of a word not yet present in the lexical database of the system, which therefore must be entered once by tapping each letter in order to add it to the database. To maximize the user's potential for rapid text entry, the system needs to accommodate a wide variety of errors in the entry of word input gestures (“input paths”) and still determine and produce the correctly spelled word intended by the user. Erroneous input paths are an almost inevitable result of any text input system, as each user will tend to try to input text faster and faster, until an unacceptable number of errors limits the effective rate of text entry. The robustness of the present invention with respect to erroneous and incorrect input paths is an important characteristic of the present system that allows much faster entry of input paths since there is a greatly reduced need for precision. There is also a need to accommodate errors caused by “the environment”—for example, such as trying to use a touch-screen device in a moving car, where the stylus may bounce unintentionally off of the touch-screen while trying to enter text. There is also a need to facilitate simple and rapid recovery from misrecognition errors, where the intended word was identified by the system but a different word was actually output due to having a higher priority. Finally, to accommodate greater speed in the entry of gestures, there is a need to allow the user to be less precise in entering gestures without sacrificing the ability to consistently interpret the user's gestures in such a way that they are correctly matched with the intended word. This includes a need for the system to be able to frequently identify a correctly spelled word from an input path corresponding to an incorrect spelling of the word, as well as the need to accommodate a wide variety of path tracing errors including inadvertent gross errors in entering a path for an intended word.
It is also relevant to consider that, in contrast to the usual expectations for new hardware technology, handheld touch-screen devices are in some instances being developed with slower rather than faster processors. This is particularly true for touch-screen devices that are also cellular phones, as it is very important to create phone devices that extend the battery life as long as possible on a single charge, and slower processors help in that regard. Thus, it is very important to create a system that uses the most efficient means possible to identify the intended word as often as possible given these constrained resources. Furthermore, mass-market devices such as touch-screen cellular phones are designed to be able to be produced as cheaply as possible, which also tends to put a premium on the use of memory resources by applications which target these devices, so that minimizing the size of such applications (and in particular the databases required for such applications) is another critical goal.
The present invention solves all of the above problems. As described below, the various aspects of the present invention combine to yield an unexpected result—that visually guided gesturing with reference to a displayed virtual keyboard is far faster than tapping, and can be used to enter words from a vocabulary that is large enough (for example, over 60,000 words in one implementation of a system for the English language) that the user only needs to resort to tapping to enter an unusual name or word the first time that word is entered using the system. This initial entry of a new word can reasonably be viewed as a process that is outside the normal text entry method, since once such a word has been tapped in it is then known to the system and can thereafter be entered using gesturing. The present invention, however, also includes aspects with respect to the tapping of words that improve upon anything known in the prior art. And, as will be shown in the following description, the present system allows the user to easily enter distinct words that “collide” because they otherwise map to the same basic gesture, or input path. Also importantly, the method presented can be implemented such that the processing resources and memory required are within acceptable limits for virtually all of the handheld touch-screen devices being developed.